home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Celestin Apprentice 7
/
Apprentice-Release7.iso
/
Environments
/
Small Eiffel 0.4.8
/
lib_show
/
pyramid.e
< prev
next >
Wrap
Text File
|
1997-04-13
|
5KB
|
224 lines
-- Part of SmallEiffel -- Read DISCLAIMER file -- Copyright (C)
-- Dominique COLNET and Suzanne COLLIN -- colnet@loria.fr
--
class PYRAMID
--
-- Solving the problem of the Pyramid for small pyramid only.
--
--| This program uses the back-tracking method.
--| Its goal is to try to fill a pyramid by making a substraction
--| between two succesive columns and to take its absolute value.
--| The result is put on the next line.
--| Example :
--| 6 14 15 3 13
--| 8 1 12 10
--| 7 11 2
--| 4 9
--| 5
--
-- See also pyramid2, which run faster than this first solution.
inherit ANY redefine print_on end;
creation
make
feature {ANY}
size : INTEGER;
make is
do
std_output.put_string("Want to compute a small pyramid ?%N%
%Enter a small number (> 1) : ");
std_input.read_integer;
size := std_input.last_integer;
if size <= 1 then
std_output.put_string("You feel sick ?%N");
elseif size > biggest_one then
std_output.put_string("Value too big for this method.%N");
else
!!elem.make(1,max);
if fill_up(1) then
std_output.put_string("Full pyramid :%N");
print_on(std_output);
else
std_output.put_string("Unable to fill_up such one.%N");
end;
end;
end; -- make
max : INTEGER is
do
Result := (size * (size + 1)) // 2;
end; -- max
print_on(file: STD_FILE_WRITE) is
local
lig,col,nb : INTEGER;
do
from
lig := 1;
col := 1;
nb := 0;
until
nb = max
loop
if col = 1 then
file.put_new_line;
end;
file.put_integer(elem.item(indice(lig,col)));
file.put_string(" ");
if col = size - lig + 1 then
col := 1 ;
lig := lig + 1 ;
else
col := col + 1;
end;
nb := nb + 1;
end;
file.put_new_line;
end; -- print_on
belongs_to(nb : INTEGER): BOOLEAN is
require
nb_trop_petit: nb >= 1;
nb_trop_grand: nb <= max;
local
i : INTEGER;
trouve : BOOLEAN;
do
from
i := 1;
trouve := false;
until
((i > max) or trouve)
loop
trouve := (nb = elem.item(i));
i := i + 1;
end;
Result := trouve;
end; -- belongs_to
propagate (col, val_column_1: INTEGER): BOOLEAN is
require
val_column_1 >= 1;
val_column_1 <= max;
col >= 1;
col <= size;
local
stop : BOOLEAN;
lig : INTEGER;
val : INTEGER;
do
if belongs_to(val_column_1) then
Result := false ;
else
from
elem.put(val_column_1,indice(1,col));
lig := 1;
val := val_column_1;
stop := false;
Result := true;
until
stop
loop
lig := lig + 1;
if lig > col then
stop := true;
else
val := val - elem.item(indice(lig-1,col-lig+1));
if val < 0 then -- valeur absolue !
val := - val ;
end;
if belongs_to(val) then
clear_column(col);
stop := true;
Result := false;
else
elem.put(val,indice(lig,col-lig+1));
end;
end;
end;
end;
end; -- propagate
fill_up (col : INTEGER) : BOOLEAN is
require
col >= 1;
local
stop : BOOLEAN;
nb : INTEGER;
do
if col > size then
Result := true;
else
from
stop := false;
nb := max;
until
stop
loop
if belongs_to(nb) then
nb := nb - 1;
stop := (nb = 0);
elseif propagate(col,nb) then
if fill_up(col + 1) then
stop := true;
else
clear_column(col);
nb := nb - 1;
stop := (nb = 0);
end;
else
nb := nb - 1;
stop := (nb = 0);
end;
end;
Result := (nb > 0);
end;
end; -- fill_up
feature {NONE}
elem: ARRAY[INTEGER];
case_vide : INTEGER is 0;
biggest_one: INTEGER is 10;
indice (lig,col : INTEGER): INTEGER is
require
lig_trop_petit: lig >= 1 ;
lig_trop_grand: lig <= size ;
col_trop_petit: col >= 1 ;
col_trop_grand: col <= size ;
local
l : INTEGER ;
do
l:= size - lig + 1;
Result := max - ((l * (l + 1)) // 2) + col;
ensure
Result >= 1 ;
Result <= max ;
end; -- indice
clear_column (col : INTEGER) is
require
col >= 1;
col <= size;
local
lig : INTEGER;
do
from
lig := 1;
until
lig > col
loop
elem.put(case_vide,indice(lig,col-lig+1));
lig := lig + 1;
end;
end; -- clear_column
end -- class PYRAMID